#include "pfs_functions.h"
#include <vector>
#include <ctime>
#include <climits>
#include <algorithm>

#include "pfs_item.h"
#include "pfs_base.h"
#include "random_gen.h"

using namespace std;

/* FuntionName(typename var_name) {
 *  // body
 * }
 *
 * 2 space as tab
 */

// Funtions look likes:

vector<Solution> MatingSelection(const vector<Answer>&, const int);
vector<Solution> Reproduce(const vector<Solution>&);
Solution Mutate(const Solution&);
vector<Answer>EnvironmentalSelection(const vector<Answer>&);
Answer LocalSearch (const Solution&, const PFS_Item&);

// Don't overwrite this templates
// Write new functions with new name but same interface
// like: Solution CoolMutate(const Solution&) { ... }

#pragma region MatingSelection

//Windowing + Roulette wheel selection
vector<Solution> WindowingRouletteMatingSelection(const vector<Answer>& answers,  const int solutions_size){
	
	vector<Solution> selected_solutions;

	int min_score = INT_MAX;
	for(int i = 0 ; i < (signed)answers.size(); i++){
		if(answers[i].score_ < min_score) min_score = answers[i].score_;
	}

	vector<double> roulette;
	roulette.push_back(0);
	double title_fitness = 0;
	double now_title_fitness = 0;
	for(int i = 0 ; i < (signed)answers.size(); i++){
		roulette.push_back((double)(answers[i].score_-min_score));
		title_fitness += (answers[i].score_-min_score);
	}
	for(int i = 1 ; i < (signed)roulette.size(); i++){
		now_title_fitness += roulette[i];
		roulette[i] = now_title_fitness / title_fitness;
	}

	while(selected_solutions.size() != solutions_size){
		double pro = rand()%1000 / 1000.0;
		for(int i = 0 ; i < (signed)roulette.size()-1; i++){
			if(pro >= roulette[i] && pro <= roulette[i+1]){
				selected_solutions.push_back(answers[i].solution_);
				break;
			}
		}
	}

	return selected_solutions;
}

//Tournament selection
vector<Solution> TournamentSelection(const vector<Answer>& answers,  const int solutions_size){
	
	vector<Solution> selected_solutions;

	int fir_select,sec_select;

	while(selected_solutions.size() < solutions_size){
		fir_select = rand() % answers.size();
		sec_select = rand() % answers.size();
		if(answers[fir_select].score_ > answers[sec_select].score_){
			selected_solutions.push_back(answers[fir_select].solution_);
		}
		else{
			selected_solutions.push_back(answers[sec_select].solution_);
		}
	}

	return selected_solutions;
}

#pragma endregion MatingSelection

#pragma region Reproduce

void OXAndLOXFixed(int fixed_index, int fixed_size, Solution& offspring_one, Solution& offspring_two){
	for(int i = 0 ; i < (signed)offspring_one.size()  ; i++){
		if(i < fixed_index || i >= (fixed_index+fixed_size))
		offspring_one[i] = -1;
		offspring_two[i] = -1;
	}
}

void OXSetEndGene(Solution& offspring,const Solution& parent){
	
	if(offspring[offspring.size()-1] != -1)
		return;
	
	for(int i = 0 ; i < (signed)offspring.size(); i++)
	{
		if(find(offspring.begin(), offspring.end(), parent[i]) == offspring.end())
		{
			offspring[offspring.size()-1] = parent[i];
			break;
		}
	}
}

void OXAndLOXSet(Solution& offspring, const Solution& parent){
	size_t index_offspring = 0, index_parent = 0;
	while(index_offspring < offspring.size())
	{
		if(offspring[index_offspring] != -1)
		{
			index_offspring++;
		}
		else if(find(offspring.begin(), offspring.end(), parent[index_parent]) == offspring.end())
		{
			offspring[index_offspring] = parent[index_parent];
			index_offspring++;
			index_parent++;
		}
		else
		{
			index_parent++;
		}
	}
}

//Order crossover
vector<Solution> OXReproduce(const vector<Solution>& parents){
	
	vector<Solution> offsprings(parents);

	int fixed_index = 2, fixed_size = 3;

	for(int i = 0 ; i < (signed)parents.size(); i+=2)
	{
		OXAndLOXFixed(fixed_index,fixed_size,offsprings[i],offsprings[i+1]);

		OXSetEndGene(offsprings[i],parents[i+1]);
		OXSetEndGene(offsprings[i+1],parents[i]);
		
		OXAndLOXSet(offsprings[i],parents[i+1]);
		OXAndLOXSet(offsprings[i+1],parents[i]);
	}

	return offsprings;
}

//Linear order crossover
vector<Solution> LOXReproduce(const vector<Solution>& parents){

	vector<Solution> offsprings(parents);

	int fixed_index = 2, fixed_size = 3;

	for(int i = 0 ; i < (signed)parents.size(); i+=2)
	{
		OXAndLOXFixed(fixed_index,fixed_size,offsprings[i],offsprings[i+1]);

		OXAndLOXSet(offsprings[i],parents[i+1]);
		OXAndLOXSet(offsprings[i+1],parents[i]);
	}

	return offsprings;
}

//Cycle Reproduce
vector<Solution> CycleReproduce(const vector<Solution>& solutionset){
    
	int num=0, pos=0, search_pos=0;
	int times = solutionset.size() / 2;
	vector<int> change_idx;
	vector<Solution> new_solutionset(solutionset);
    
	while(times--){
		change_idx.clear();
		do{
			while(new_solutionset[num][pos]!=new_solutionset[num+1][search_pos]){ pos++; }
			change_idx.push_back(pos);
			search_pos = pos;
			pos = 0;
		}while(search_pos!=0);
        
		for(size_t i=0; i<change_idx.size(); i++ ){
			swap(new_solutionset[num][change_idx[i]],new_solutionset[num+1][change_idx[i]]);
		}
		num+=2;
	}
	return new_solutionset;
}

//Partially Mapped Crossover
vector<Solution> PMReproduce(const vector<Solution>& solutionset){
	vector<Solution> new_solutionset(solutionset);
	Solution tmp_sol;
	int num = 0;
	int times = new_solutionset.size()/2;
	const int sol_size = new_solutionset[num].size();
	const int cut_begin = sol_size / 3; // about 1/3
	const int cut_end = sol_size * 2 / 3; // about 2/3
	
	while(times--){
		for(int i=cut_begin; i<cut_end; i++ ){
			swap(new_solutionset[num][i], new_solutionset[num+1][i]);
		}
		num+=2;
	}
	
  for(size_t idx=0; idx<new_solutionset.size(); idx++){
		for(int i=0; i<sol_size; i++){
			if(i>=cut_begin && i<cut_end ) continue;
			else{
				for(int j=cut_begin; j<cut_end; j++){
					if(new_solutionset[idx][i]==new_solutionset[idx][j]){
						new_solutionset[idx][i]=solutionset[idx][j];
						i--; //check this element again
						break;
					}
				}
			}
		}
	}
	
	return new_solutionset;
}

//POX Reproduce
vector<Solution> POXReproduce(const vector<Solution>& parents){

	vector<Solution> offsprings(parents);
	
	int fix_job_index, fix_job;
	vector<int>::iterator temp;

	for(int i = 0 ; i < (signed)parents.size(); i+=2)
	{
		fix_job_index = rand() % offsprings[i].size();
		fix_job = offsprings[i][fix_job_index];

		temp = find(offsprings[i+1].begin(), offsprings[i+1].end(), fix_job);

		offsprings[i].erase( offsprings[i].begin() + fix_job_index );
		offsprings[i].insert( offsprings[i].begin() + (temp-offsprings[i+1].begin()) , fix_job);

		offsprings[i+1].erase( temp );
		offsprings[i+1].insert( offsprings[i+1].begin() + fix_job_index , fix_job);
	}

	return offsprings;
}

//PPX Reproduce
vector<Solution> PPXReproduce(const vector<Solution>& solutionset){
	int times = solutionset.size();
	int num = 0, fir_pos = 0, sec_pos = 0;
	const int sol_size = solutionset[num].size();
   const int num_size = solutionset.size();
	bool *is_firsol_del = new bool [sol_size];
	bool *is_secsol_del = new bool [sol_size];
	vector<Solution> new_solutionset;
	Solution new_solution;
    
	while(times--){
		new_solution.clear();
		fill( is_firsol_del, is_firsol_del + sol_size, 0 );
		fill( is_secsol_del, is_secsol_del + sol_size, 0 );
		fir_pos = 0; 
		sec_pos = 0;
		
		while(new_solution.size() != sol_size){
			while(is_firsol_del[fir_pos]){ fir_pos++; }
			while(is_secsol_del[sec_pos]){ sec_pos++; }
			
			if(rand()%2){
				new_solution.push_back(solutionset[(num+1)%num_size][sec_pos]);
				is_secsol_del[sec_pos]=true;
				for(int i=0; i<sol_size; i++){
					if(solutionset[num][i]==solutionset[(num+1)%num_size][sec_pos]) is_firsol_del[i]=true;
				}
			}
			else{ 
				new_solution.push_back(solutionset[num][fir_pos]); 
				is_firsol_del[fir_pos]=true;
				for(int i=0; i<sol_size; i++){
					if(solutionset[(num+1)%num_size][i]==solutionset[num][fir_pos]) is_secsol_del[i]=true;
				}
			}
		}
		new_solutionset.push_back(new_solution);
		num+=1;
	}
	delete [] is_firsol_del;
	delete [] is_secsol_del;
	return new_solutionset;
}

#pragma endregion Reproduce

#pragma region Mutate

//Random swap two genes
Solution RandomSwapMutate(const Solution& solution){

	Solution new_solutions(solution);

	int fir_change = rand() % new_solutions.size();
	int sec_change = rand() % new_solutions.size();

	swap(new_solutions[fir_change],new_solutions[sec_change]);
	return new_solutions;
}

//Random insertion for mutation
int pre_offest(int x, size_t s) {
  --x;
  if(x < 0) { return x + s; }
  return x;
}

Solution RandomInsertMutate(const Solution& o_solution){
	Solution solution(o_solution);
	int pick_pos = rand() % solution.size();
  int ins_pos = rand() % solution.size();
	int tmp = solution[pick_pos];

  int diff = pick_pos-ins_pos;
  if (diff < 0) {
    diff = pick_pos + solution.size() - ins_pos;
  }
    
	for (int i = diff, j = pick_pos ; i >= 0 ;
      --i, j = pre_offest(j, solution.size())) {
    solution[j] = solution[pre_offest(j, solution.size())];
  }
    
	solution[ins_pos] = tmp;
	return solution;
}

#pragma endregion Mutate

#pragma region LocalSearch

// II Local search
Solution RandomSwapneighbor(const Solution& solution){
	Solution new_solution(solution);
	int pos = rand() % new_solution.size();
	int change_pos = rand() % new_solution.size();
	swap( new_solution[pos], new_solution[change_pos] );
	return new_solution;
}

Answer IILocalSearch (const Solution& solution, const PFS_Item& pfs_item, clock_t time_limit){
	const int loop_times = 10000;
	const int neighbor_size = 4;
	
	Answer answer(solution, Score(solution, pfs_item));
	Solution sol_neighbor[neighbor_size];
	int cur_score;
	int times = loop_times;
	clock_t start = clock();
	
	while(times-- && clock()-start < time_limit ){
		for( int i=0; i<neighbor_size; i++ ){
			sol_neighbor[i] = RandomSwapneighbor(solution);
			cur_score = Score(sol_neighbor[i], pfs_item);
			if( cur_score > answer.score_ ){
				answer.solution_ = sol_neighbor[i];
				answer.score_ = cur_score;
			}
		}
	}
	
	return answer;
	
}

//TS Local search
bool compare (const Answer& i,const Answer& j){
	return (i.score_ > j.score_); 
}

Answer TSLocalSearch (const Solution& solution, const PFS_Item& pfs_item, clock_t time_limit){
	
	Answer answer(solution, Score(solution, pfs_item));
	
	clock_t start;

	const int tabulist_size = solution.size();
	vector<Solution> tabulist;

	const int neighbor_size = 4;
	vector<Answer> neighbors;

	tabulist.assign(tabulist_size,solution);
	neighbors.assign(neighbor_size,answer);

	start = clock();
	while(clock()-start <= time_limit){
    	for( int i = 0 ; i < neighbor_size ; i++ ){
			neighbors[i].solution_ = RandomSwapneighbor(solution);
			neighbors[i].score_ = Score(neighbors[i].solution_, pfs_item);
		}
		
		sort (neighbors.begin(), neighbors.end(), compare);

		for(int i = 0 ; i < neighbor_size ; i++){
			if(find(tabulist.begin(), tabulist.end(), neighbors[i].solution_) == tabulist.end() && answer.score_ < neighbors[i].score_){
				answer.solution_ = neighbors[i].solution_;
				answer.score_ = neighbors[i].score_;

				for(int i = 0 ; i < tabulist_size - 1 ; i++){
					tabulist[i] = tabulist[i+1];
				}
				tabulist[tabulist_size - 1] = answer.solution_;

				break;
			}
		}
	}//end while
	
	return answer;
	
}

Answer SALocalSearch(const Solution& o_solution, const PFS_Item& pfs_item, clock_t time_limit) {	
  Solution solution = o_solution;
  RandomGenReal<double> randomDouble(0.0 , 1.0);
  double kStartTemp = 1000.0;
  double kCoolRate = 0.8;
  double kFinalTemperature = 0.1; 

	double high_temperature = kStartTemp;
	double coolRate = kCoolRate;
	const double kCoolRateMax = 0.9998;
	const int kMaxNumJump = 2;
  const int kIterateLength = 100;

  Answer best_ans(solution, Score(solution, pfs_item));
  int scoreNow = best_ans.score_;

  clock_t start = clock();
	
	while(true) {
		double temperature = high_temperature;
		while(temperature > kFinalTemperature) {
			int jump_counter = 0;

			for (int i = 0 ; i < kIterateLength  ; ++i) {
        if (clock() - start > time_limit) {return best_ans;}
				if (jump_counter >= kMaxNumJump) break;

				Solution neighbor = RandomSwapMutate(solution);
        int neighborScore = Score(neighbor, pfs_item);
				double doorsill = randomDouble();
				if (neighborScore <= scoreNow ||
						exp((scoreNow - neighborScore) / temperature) > doorsill) {
				
							solution = neighbor;
							scoreNow = neighborScore;

              if (scoreNow < best_ans.score_)
                best_ans = Answer(solution, scoreNow);

							++jump_counter;
				}
			}
			temperature *= coolRate;
		}
		coolRate += (1.0 - coolRate) / 2.0;
		coolRate = std::min(kCoolRateMax, coolRate);
	}

  return best_ans;
}

#pragma endregion LocalSearch


auto GetRandomSolution(const PFS_Item& pfs_item) -> Solution {
	Solution randomSolution;
	Solution solutionNow;

	for(int i = 0 ; i < pfs_item.job_num() ; ++i){
		solutionNow.push_back(i);
	}

	for(int i = pfs_item.job_num() ; i > 0 ; --i)	{
		// for(int i = pfs_item_.job_num() - 1 ; i >= 0 ; --i)	{
		 //int randomIndex = RandomGen<int>(0,i)();
		int randomIndex = rand() % i;
		randomSolution.push_back(solutionNow[randomIndex]);
		solutionNow.erase(solutionNow.begin() + randomIndex);
	}

	return randomSolution;
}

vector<Solution> InitPopulation(const PFS_Item& pfs_item, size_t size) {
  vector<Solution> init_pop(size);
  for (auto& e : init_pop) {
    e = GetRandomSolution(pfs_item);
  }

  return init_pop;
}

vector<Answer>
Evaluate(const std::vector<Solution>& solutions, const PFS_Item& pfs_itme){
  vector<Answer> answers;
  for (const Solution& e : solutions) {
    answers.push_back(Answer(e, Score(e, pfs_itme)));
  }
  return answers;
}

vector<Solution>
AnswersToSolutions(const std::vector<Answer>& answers) {
  vector<Solution> v(answers.size());
  for (size_t i = 0 ; i < v.size() ; ++i) {
    v[i] = answers[i].solution_;
  }
  return v;
}

std::vector<Solution>
EnvironmentalSelection(std::vector<Answer> answers, size_t size) {
  using std::sort;

  if(size > answers.size()) {
    perror("EnvironmentalSelection: wrong size");
  }

  sort(answers.begin(), answers.end(), [](const Answer& a, const Answer& b) {
    return a.score_ < b.score_;
  });
  answers.resize(size, answers.back());

  vector<Solution> v;
  for(auto e : answers) {
    v.push_back(e.solution_);
  }

  return v;
}
